package linkedin;

import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * Created by Tzachi on 26/10/2014.
 * <p>
 * In "the 100 game," two players take turns adding, to a running
 * total, any integer from 1..10. The player who first causes the running
 * total to reach or exceed 100 wins.
 * What if we change the game so that players cannot re-use integers?
 * For example, if two players might take turns drawing from a common pool of numbers
 * of 1..15 without replacement until they reach a total >= 100. This problem is
 * to write a program that determines which player would win with ideal play.
 * <p>
 * Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)",
 * which returns true if the first player to move can force a win with optimal play.
 * <p>
 * Your priority should be programmer efficiency; don't focus on minimizing
 * either space or time complexity.
 */
public class CanIWin {

    public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= maxChoosableInteger; i++) {
            set.add(i);
        }
        return recursiveWin(set, desiredTotal, 0, true);
    }

    public static boolean recursiveWin(Set<Integer> integers, int desiredTotal, int currentTotal,
                                       boolean start) {
        if (integers.isEmpty()) {
            return false;
        }
        for (Integer nextInt : integers) {
            if (nextInt + currentTotal >= desiredTotal) {
                if (start){
                    System.out.println(nextInt);
                }
                return start;
            }
        }
        for (Integer nextInt : integers) {
            Set<Integer> current = new HashSet<>(integers);
            current.remove(nextInt);
            if (recursiveWin(current, desiredTotal, currentTotal + nextInt, !start)) {
                System.out.println(nextInt);
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canIWin(5, 8));
    }

}
